P3831 [SHOI2012]回家的路

这道题显然是最短路，但是似乎转向时不好处理，于是我们要用到分层图。

实现很简单，建立两层图，第一层记录横向边，第二层记录纵向边，相同的关键点两层图连一条费用为1的边。

还有，这道题只需要在关键点之间连边（非关键点无法转向，连了也没用），路径长度为坐标差*2。

对于起点和终点，我们把它也当作关键点，但转向只需0的费用。

#include <cstdio>
#include <cstring>
#include <queue>
#include <iostream>
#include <algorithm>
using namespace std;
#define INF 0x3f3f3f3f

const int MAXM = 100005;
int n , m;
struct Point{
    int x , y , id;
}imp[ MAXM + 5 ];
bool cmpx( const Point &a , const Point &b ) {
    return a.x < b.x || ( a.x == b.x && a.y < b.y );
}
bool cmpy( const Point &a , const Point &b ) {
    return a.y < b.y || ( a.y == b.y && a.x < b.x );
} 
bool cmpi( const Point &a , const Point &b ) {
	return a.id < b.id;
}

struct node{
    int v , w;
    bool operator > ( const node &x ) const {
        return w > x.w;
    }
};
vector< node > Graph[ 8 * MAXM + 5 ];
int dist[ 2 * MAXM + 5 ];
bool vis[ 2 * MAXM + 5 ];
int Dijkstra( int s , int t ) {
    priority_queue< node , vector< node > , greater< node > > Que;
    memset( dist , INF , sizeof( dist ) );
    memset( vis , 0 , sizeof( vis ) );

    Que.push( { s , dist[ s ] = 0 } );
    while( !Que.empty( ) ) {
        int u = Que.top( ).v; Que.pop( );
        
        if( vis[ u ] ) continue;
		vis[ u ] = 1;
		
        for( int i = 0 ; i < Graph[ u ].size( ) ; i ++ ) {
            int v = Graph[ u ][ i ].v , w = Graph[ u ][ i ].w;
            if( dist[ v ] > dist[ u ] + w ) {
                dist[ v ] = dist[ u ] + w;
                Que.push( { v , dist[ v ] } );
            }
        }
    }
    return dist[ t ] == INF ? -1 : dist[ t ];
}

int main( ) {
    scanf("%d %d",&n,&m);
    for( int i = 1 ; i <= m ; i ++ )
        scanf("%d %d", &imp[ i ].x , &imp[ i ].y ) , imp[ i ].id = i;
    m ++ , scanf("%d %d", &imp[ m ].x , &imp[ m ].y ) , imp[ m ].id = m;
    m ++ , scanf("%d %d", &imp[ m ].x , &imp[ m ].y ) , imp[ m ].id = m;

    sort( imp + 1 , imp + m + 1 , cmpx );
    for( int i = 1 ; i <= m ; i ++ ) {
        int dex1 = imp[ i ].id , dex2 = imp[ i + 1 ].id;
        if( imp[ i ].x != imp[ i + 1 ].x ) continue;
        Graph[ dex1 ].push_back( { dex2 , 2 * ( imp[ i + 1 ].y - imp[ i ].y ) } );
        Graph[ dex2 ].push_back( { dex1 , 2 * ( imp[ i + 1 ].y - imp[ i ].y ) } );
    }
    
    sort( imp + 1 , imp + m + 1 , cmpy );
    for( int i = 1 ; i <= m ; i ++ ) {
        int dex1 = imp[ i ].id + MAXM , dex2 = imp[ i + 1 ].id + MAXM;
        if( imp[ i ].y != imp[ i + 1 ].y ) continue;
        Graph[ dex1 ].push_back( { dex2 , 2 * ( imp[ i + 1 ].x - imp[ i ].x ) } );
        Graph[ dex2 ].push_back( { dex1 , 2 * ( imp[ i + 1 ].x - imp[ i ].x ) } );
    }
    
	sort( imp + 1 , imp + m + 1 , cmpi );
    for( int i = 1 ; i <= m ; i ++ ) {
        int f = ( i <= m - 2 ) , dex1 = imp[ i ].id , dex2 = imp[ i ].id + MAXM;
        Graph[ dex1 ].push_back( { dex2 , f } );
        Graph[ dex2 ].push_back( { dex1 , f } );
    }
    printf("%d", Dijkstra( m - 1 , m ) );
    return 0;
}